class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        int memo[m][n];
        memo[m - 1][n - 1] = max(0, - dungeon[m - 1][n - 1]) ;
        for (int i = m - 2; i >= 0; i--)
            memo[i][n - 1] = max(memo[i + 1][n - 1] - dungeon[i][n - 1], 0);
        for (int i = n - 2; i >= 0; i--)
            memo[m - 1][i] = max(memo[m - 1][i + 1] - dungeon[m - 1][i], 0);
        for (int i = m - 2; i >= 0; i--)
            for (int j = n - 2; j >= 0; j--)
                memo[i][j] = max(min(memo[i][j + 1], memo[i + 1][j]) - dungeon[i][j], 0);
        return memo[0][0] + 1;
    }
};
